home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 42 / Amiga Format AFCD42 (Issue 126, Aug 1999).iso / -serious- / comms / other / slrn / slrn_src / src / hash.c < prev    next >
C/C++ Source or Header  |  1999-05-14  |  5KB  |  244 lines
  1. /* Copyright (c) 1998 John E. Davis (davis@space.mit.edu)
  2.  *
  3.  * This file is part of slrn.
  4.  *
  5.  * Slrn is free software; you can redistribute it and/or modify it
  6.  * under the terms of the GNU General Public License as published by the
  7.  * Free Software Foundation; either version 2, or (at your option) any
  8.  * later version.
  9.  * 
  10.  * Slrn is distributed in the hope that it will be useful, but WITHOUT
  11.  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12.  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13.  * for more details.
  14.  * 
  15.  * You should have received a copy of the GNU General Public License
  16.  * along with Slrn; see the file COPYING.  If not, write to the Free
  17.  * Software Foundation, 59 Temple Place - Suite 330, 
  18.  * Boston, MA  02111-1307, USA.
  19.  */
  20.  
  21. #include "config.h"
  22. #ifndef SLRNPULL_CODE
  23. # include "slrnfeat.h"
  24. #endif
  25.  
  26. #include <stdio.h>
  27. #include <string.h>
  28.  
  29. #include <slang.h>
  30. #include "jdmacros.h"
  31.  
  32. #include "hash.h"
  33.  
  34. unsigned long slrn_compute_hash (unsigned char *s, unsigned char *smax)
  35. {
  36.    register unsigned long h = 0, g;
  37.    register unsigned long sum = 0;
  38.    
  39.    while (s < smax)
  40.      {
  41.     sum += *s++ | 0x20;           /* case-insensitive */
  42.     
  43.     h = sum + (h << 3);
  44.     if ((g = h & 0xE0000000U) != 0)
  45.       {
  46.          h = h ^ (g >> 24);
  47.          h = h ^ g;
  48.       }
  49.      }
  50.    return h;
  51. }
  52.  
  53. #if SLRN_HAS_MSGID_CACHE
  54. typedef struct Msg_Id_Cache_Type
  55. {
  56.    char *msgid;
  57.    char *newsgroup;
  58.    struct Msg_Id_Cache_Type *next;
  59. #ifdef SLRNPULL_CODE
  60.    unsigned int num;
  61. #endif
  62. }
  63. Msg_Id_Cache_Type;
  64.  
  65. typedef struct Newsgroup_Cache_Type
  66. {
  67.    char *newsgroup;
  68.    struct Newsgroup_Cache_Type *next;
  69. }
  70. Newsgroup_Cache_Type;
  71.  
  72. #define MAX_MSGID_HASH    8017
  73. #define MAX_NG_HASH    2909
  74.  
  75. static Msg_Id_Cache_Type *Msg_Id_Cache [MAX_MSGID_HASH];
  76. static Newsgroup_Cache_Type *Newsgroup_Cache [MAX_NG_HASH];
  77.  
  78. static unsigned int simple_hash (unsigned char *s, unsigned char *smax, 
  79.                  unsigned int mod)
  80. {
  81.    register unsigned int h = 0;
  82.    
  83.    while (s < smax)
  84.      {
  85.     h = ((h << 5) + *s) % mod;
  86.     s++;
  87.      }
  88.    return h;
  89. }
  90.  
  91. static char *allocate_newsgroup (char *newsgroup)
  92. {
  93.    Newsgroup_Cache_Type *node;
  94.    unsigned int hash_index;
  95.    unsigned int len;
  96.    
  97.    len = strlen (newsgroup);
  98.    
  99.    hash_index = simple_hash ((unsigned char *) newsgroup,
  100.                  (unsigned char *) newsgroup + len,
  101.                  MAX_NG_HASH);
  102.    
  103.    node = Newsgroup_Cache [hash_index];
  104.    
  105.    while (node != NULL)
  106.      {
  107.     if (!strcmp (node->newsgroup, newsgroup))
  108.       return node->newsgroup;
  109.     node = node->next;
  110.      }
  111.    
  112.    node = (Newsgroup_Cache_Type *) SLMALLOC (sizeof (Newsgroup_Cache_Type));
  113.    if (node == NULL) return NULL;
  114.    if (NULL == (node->newsgroup = (char *) SLMALLOC (len + 1)))
  115.      {
  116.     SLFREE (node);
  117.     return NULL;
  118.      }
  119.    strcpy (node->newsgroup, newsgroup);
  120.    
  121.    node->next = Newsgroup_Cache [hash_index];
  122.    Newsgroup_Cache [hash_index] = node;
  123.    
  124.    return node->newsgroup;
  125. }
  126.  
  127.    
  128.    
  129. static Msg_Id_Cache_Type *allocate_msgid_node (char *msgid, unsigned int msgid_len, 
  130.                            char *newsgroup)
  131. {
  132.    Msg_Id_Cache_Type *node;
  133.    char *buf;
  134.    
  135.    newsgroup = allocate_newsgroup (newsgroup);
  136.    if (newsgroup == NULL)
  137.      return NULL;
  138.    
  139.    buf = (char *) SLMALLOC (msgid_len + 1);
  140.    if (buf == NULL) return NULL;
  141.    strcpy (buf, msgid);
  142.    
  143.    node = (Msg_Id_Cache_Type *) SLMALLOC (sizeof (Msg_Id_Cache_Type));
  144.    if (node == NULL)
  145.      {
  146.     SLFREE (buf);
  147.     return NULL;
  148.      }
  149.    node->msgid = buf;
  150.    node->newsgroup = newsgroup;
  151.    return node;
  152. }
  153.  
  154. static int Dont_Grow = 0;
  155. static Msg_Id_Cache_Type *is_msgid_cached (char *msgid, char *newsgroup,
  156.                        unsigned int num, int add)
  157. {
  158.    Msg_Id_Cache_Type *node;
  159.    unsigned int hash_index;
  160.    unsigned int msgid_len;
  161.    
  162. #ifndef SLRNPULL_CODE
  163.    (void) num;
  164. #endif
  165.  
  166.    msgid_len = strlen (msgid);
  167.    
  168.    hash_index = simple_hash ((unsigned char *) msgid, 
  169.                  (unsigned char *) msgid + msgid_len,
  170.                  MAX_MSGID_HASH);
  171.  
  172.    node = Msg_Id_Cache [hash_index];
  173.    
  174.    while (node != NULL)
  175.      {
  176.     if (!strcmp (node->msgid, msgid))
  177.       return node;
  178.     node = node->next;
  179.      }
  180.    
  181.    if (add && (Dont_Grow == 0) && (newsgroup != NULL))
  182.      {
  183.     node = allocate_msgid_node (msgid, msgid_len, newsgroup);
  184.     
  185.     if (node == NULL) Dont_Grow = 1;
  186.     else
  187.       {
  188. #ifdef SLRNPULL_CODE
  189.          node->num = num;
  190. #endif
  191.          node->next = Msg_Id_Cache [hash_index];
  192.          Msg_Id_Cache [hash_index] = node;
  193.       }
  194.      }
  195.    
  196.    return NULL;
  197. }
  198.  
  199. char *slrn_is_msgid_cached (char *msgid, char *newsgroup, int add)
  200. {
  201.    Msg_Id_Cache_Type *node;
  202.    
  203.    node = is_msgid_cached (msgid, newsgroup, 0, add);
  204.  
  205.    if (node != NULL)
  206.      return node->newsgroup;
  207.  
  208.    return NULL;
  209. }
  210.    
  211. #endif                       /* SLRN_HAS_MSGID_CACHE */
  212.  
  213. #if 0
  214. #define SIZE 1250
  215. unsigned int bin[SIZE];
  216.  
  217. int main (int argc, char **argv)
  218. {
  219.    unsigned char buf[0x7FFF];
  220.    unsigned char *b, ch;
  221.    unsigned long hash;
  222.    int i;
  223.    
  224.    while (NULL != fgets ((char *) buf, sizeof (buf) - 1, stdin))
  225.      {
  226.     b = buf;
  227.     while (((ch = *b) != '!') && (ch != ':') && (ch > ' '))
  228.       b++;
  229.     
  230.     hash = slrn_compute_hash (buf, b);
  231.     hash = hash % SIZE;
  232.     
  233.     /* fprintf (stdout, "%X\n", hash); */
  234.     bin[hash] += 1;
  235.      }
  236.    
  237.    for (i = 0; i < SIZE; i++)
  238.      {
  239.     fprintf (stdout, "%d\t%d\n", i, bin[i]);
  240.      }
  241.    return 0;
  242. }
  243. #endif
  244.